The present invention is related to the field of searching, in response to a given search key such as an IP address, an entry in a data structure comprising stored tables, for determining further handling or forwarding of an item carrying that search key. The searching is based on the principle of finding in the data structure the longest-matching-prefix for a given search key. In particular, the invention is concerned with updating the stored tables in the data structure when the assignment between currently valid prefixes and associated output values or links is changed.
Currently, Internet Protocol (IP) forwarding schemes involve typically two data structures. One large central (update) data structure that is managed by software, and a smaller (forwarding) data structure that is managed by hardware.
The fast search operations are performed by hardware on the smaller (forwarding) data structure. This data structure contains only information that is relevant for the search operations and is optimized with respect to currently valid assignments between search keys (prefixes) and output information or forwarding links. Examples of such forwarding data structures were described in a paper by P. Gupta, S. Lin, and N. McKeown: xe2x80x9cRouting Lookups in Hardware at Memory Speedsxe2x80x9d (IEEE Infocom, San Francisco April 1998, Vol.3, pp. 1240-1247), and also in a paper by V. Srinivasan and G. Varghese: xe2x80x9cFast Address Lookups using Controlled Prefix Expansionxe2x80x9d (ACM Trans. Comput. Syst., Vol. 17, No. 1, February 1999, pp. 1-40). In the described systems, a treelike structure of multiple linked tables is provided for looking up prefixes, and the tables are indexed (accessed) by separate segments of the search key.
The central data structure also contains information that is necessary to perform update operations. For example, if a certain routing table entry (i.e., a prefix) is removed, the central data structure will contain information that indicates how packets that were routed according to that routing table entry, will now be routed after that routing table entry has been removed.
In case of an update operation, first the central data structure will be updated, and from the updated information included in the central data structure, the modification of the forwarding data structure will be derived. For this updating operation, no information will be read from the forwarding (smaller) data structure.
In other words: In many present-day systems for longest-matching prefix (LMP) searches in a data structure of stored assignment tables, it is usual to maintain a central data structure from which the relation between all possible prefixes or search keys and respective output values can be determined, and other more efficient data structures which are actually used for LMP searching. These more efficient data structures are optimized with respect to actually valid search keys (prefixes), to save storage space and to achieve shorter search times. When, due to new search key (prefix) assignments, an updating of the search tables is necessary, the central data structure containing all necessary information is updated in a first step. Thereafter, in a second step, the optimized, distributed data structures are updated with information obtained from the updated central data base. An updating in the local, optimized search tables would not be possible because due to the optimization. some information will be missing when updating is required.
The trend for IP routing in the Internet (and for other systems requiring LMP searches) is that the routing tables grow much larger: whereas now they contain less than 100 k entries, systems with more than 500 k entries are soon expected. Also, there will be a need for faster updating: whereas now a few updates per second are sufficient, in the future multiple thousands of updates per second will be necessary.
Due to these trends, the concept of a central data structure for the prefix assignment tables has increasing disadvantages as this will limit the number of updates that can be made, and also will require much more storage as the size of the routing tables grows significantly.
It is an object of the invention to devise a system with a data structure for finding, in response to a given search key, a matching entry in stored LMP search tables, which requires less storage than presently used search table data structure schemes. It is a further object of the invention to provide a method for updating a search data structure which requires less time for a modification of the search tables than presently used schemes, and which does not require the maintenance of a complete central data structure with all possible routing assignments.
The invented search data structure in a system for finding output information, such as directions for forwarding messages to output links, in response to search keys comprising prefixes used for longest-matching prefix searches, comprises the following features:
a) the search data structure comprising search tables is derived from a basic data structure comprising prefix tables including complete information for prefixes of variable length and respective assigned output information; b) the search data structure is subdivided into subsets of search tables which were separately derived from respective prefix tables in the complete basic data structure; and c) each subset in the search data structure comprises auxiliary information enabling a reconstruction of the respective prefix tables in the basic data structure; which features allow local or partial updating of the search data structure without maintaining the complete basic data structure of prefix tables in the system.
The invented method for updating a search data structure provided for longest-matching prefix searches when the assignment between prefixes and output information is changed by deletion of prefixes or insertion of additional prefixes, said search data structure comprising subsets of search tables separately derived from prefix tables in a basic data structure which is not maintained during normal operation, comprises the following features:
a) determining a relevant subset of search tables including at least one search table to be updated, and reading this from the search data structure; b) reconverting the relevant subset of search tables into an associated subset of prefix tables of the basic data structure, using auxiliary information contained in the relevant subset of search tables, said associated subset including at least one prefix table; c) modifying the prefix tables obtained by reconversion, according to the required changes in the prefix assignments; d) converting the subset of modified prefix tables into a derived subset of new search tables; and e) inserting the derived subset of new search tables into the search data structure, thereby replacing and/or supplementing at least one search table in the relevant subset.
This invention, for overcoming the initially mentioned problems, provides IP forwarding schemes that do not use a central data structure containing full information required for updating, together with one (or plural) smaller data structures adapted for searching and forwarding, but are based on only a single data structure that is used for both, updating as well as forwarding. In order to keep the size of this single data structure small, some form of compression can be applied.
The invention provides, in particular, the use of a single (software-operated) search table data structure for the whole system, which is optimized with respect to currently valid prefix or search key assignments but contains enough additional information to allow updating and optimizing it when the assignments are modified.
The invention has the following advantages over prior art solutions:
1) Fewer memory is needed as the total storage requirements are much smaller. The auxiliary information that is added to the search structure results in much smaller extra storage requirements than the need to maintain two data structures.
2) Update performance can be improved, since due to the smaller storage requirements, it becomes now feasible and cost effective, to implement the entire data structure in fast memory. This in contrast to prior art schemes, that typically store the basic structure in slow (and therefore cheap) memory, and the search structure in fast memory. This allows now to perform much faster update operations, since only fast memory is used too in the update process.
3) A single component, for example a search coprocessor, can now be realized that performs all update and search operations on one data structure. This allows to relieve the control processor for other tasks.
These advantages become more important with the following two trends that can be observed in the current Internet: a) the routing table sizes are growing exponentially, and b) there is a requirement for improving the performance of updating operations.
In the following, embodiments of the invention will be described with reference to the accompanying drawings.